The present invention relates to a computer system configured to store block allocation information relating to snapshot data on the system. At least some systems currently in use that provide snapshots, i.e. data from which the state of the system at a given time can be recovered, are designed to store information relating to each snapshot taken of the system, cross-referenced to each data block in the system
The number of data blocks stored in the system may be many millions or billions (or more), and as a result the overhead associated with the block allocation snapshot data can be quite large. For instance, in the “WAFL” (write-anywhere file layout) system of Network Appliance, Inc., snapshots are associated in a manner correlated with each data block, such that a very large array of information is built and stored to preserve the past states of the system. See U.S. Pat. No. 5,819,292 to Hitz et al., entitled Method for Maintaining Consistent States of a File System and for Creating User-Accessible Read-Only Copies of a File System. 
A system is accordingly needed that can reduce the amount of data needed to provide snapshot information about the blocks of data stored in a system, along with a mechanism that provides an efficient way of determining whether a given block of data is needed to preserve the history of snapshots for the system, or alternatively is a free block to which data may be written.